import java.util.HashSet;
import java.util.Set;

class Solution {
    public int missingNumber(int[] nums) {
        //解法1：抑或
        // int ret = 0;
        // for(int i = 0; i < nums.length; i++){
        //     ret ^= nums[i];
        //     ret ^= i;
        // }
        // ret ^= nums.length;
        // return ret;

        //解法2：哈希表
        // int len = nums.length;
        // int[] hash = new int[len + 1];
        // for(int i = 0; i < len; i++){
        //     hash[nums[i]] = 1;
        // }
        // for(int i = 0; i < len + 1; i++){
        //     if(hash[i] == 0){
        //         return i;
        //     }
        // }
        // return -1;

        //解法3：高斯求和
        // int sum = 0;
        // for(int i = 0; i < nums.length; i++){
        //     sum += nums[i];
        // }

        // return (0 + nums.length) * (nums.length + 1) / 2 - sum;

        //解法4：集合
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        for(int i = 0; i <= nums.length; i++){
            if(set.contains(i)){
                set.remove(i);
            }else{
                set.add(i);
            }
        }
        return set.toArray(new Integer[1])[0];
    }
}
